백준 5582번 - 공통 부분 문자열

문제 링크

코드

const readline=require('readline');

const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
});

const input=[];

rl.on('line',(line)=>{
    input.push(line);
})

rl.on('close',()=>{
    const a=input[0];
    const b=input[1];

    let max=0
    const dp=Array(a.length).fill(0)
    for(let i=0;i<b.length;i++){
        let prev=0;
        for(let j=0;j<a.length;j++){
            const temp=dp[j]
            if(b[i]==a[j]){
                dp[j]=prev+1
                max=Math.max(max,prev+1)
            }
            else{
                dp[j]=0
            }
            prev=temp
        }
    }
    console.log(max)
})

공통 부분 문자열 문제를 2차원 배열이 아닌 1차원 배열로 풀어봤다.

두 문자열의 바로 앞까지의 연속 공통 문자열 + 1이 현재 문자열까지의 연속 공통 문자열길이가 된다.

출처

위와 같은 표를 보면 한번에 이해가 된다.
즉, 문자가 같으면 dp[i-1][j-1] + 1 하면서 최장 길이를 갱신해준다.
그리고 전체에서 가장 큰 값이 최장 공통 부분 문자열의 길이가 된다.

추가로

만약 최장 공통 부분 문자열의 길이가 아니라 문자열 그 자체를 구하는 문제라면 dp 배열에서 가장 큰 값을 찾고 대각선으로 올라가면서 문자열을 찾을 수 있을 것 같다.